/*-------------------------------------------------------------------------
 *
 * hashjoin.h
 *	  哈希连接的内部结构
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/executor/hashjoin.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef HASHJOIN_H
#define HASHJOIN_H

#include "nodes/execnodes.h"
#include "port/atomics.h"
#include "storage/barrier.h"
#include "storage/buffile.h"
#include "storage/lwlock.h"


/* ----------------------------------------------------------------
 *				hash-join 哈希表结构
 *
 * 每个活动的哈希连接都有一个 HashJoinTable 控制块，它是在
 * 执行器的每查询上下文中分配的。哈希连接所需的所有其他存储
 * 都保存在私有内存上下文中，每个哈希连接有两个。这使得当
 * 我们不再需要它时，快速释放存储变得简单。 （例外：与临时
 * 文件相关的数据也存储在每查询上下文中，因为我们总是在该
 * 上下文中调用 buffile.c。）
 *
 * 哈希表上下文是父查询上下文的子上下文，确保即使连接由于
 * 错误而提前中止，它们也会在语句结束时被丢弃。 （同样，若
 * 我们创建的任何临时文件在发生错误时也会被虚拟文件管理器
 * 清理。）
 *
 * 应该在整个连接中保留的存储从 "hashCxt" 中分配，而仅在
 * 当前批处理中需要的存储则在 "batchCxt" 中分配。通过在每
 * 个批处理结束时重置 batchCxt，我们可靠而轻松地释放所有按
 * 批次分配的存储。
 *
 * 在对内关系的第一次扫描中，我们从执行器获取它的元组。
 * 如果 nbatch > 1，则不属于第一批的元组会被保存到内批次的
 * 临时文件中。外部关系的第一次扫描适用相同的语句，只是
 * 我们将元组写入外批次的临时文件。在完成第一次扫描后，
 * 我们对每个剩余批次执行以下操作：
 *	1. 从内批次文件中读取元组，加载到哈希桶中。
 *	2. 从外批次文件中读取元组，匹配哈希桶并输出。
 *
 * 如果内存中的哈希表变得太大，可以随时增加 nbatch。哈希值
 * 到批次的计算安排为，这只会导致元组进入比先前认为的后续
 * 批次，而不会进入早期批次。当我们增加 nbatch 时，我们将
 * 重新扫描哈希表，并将任何现在属于后续批次的元组转存到正
 * 确的内批次文件中。随后，在读取内批次或外批次文件时，我们
 * 可能会发现不再属于当前批次的元组；如果是这样，我们只需
 * 将它们转存到正确的批次文件中。
 * ----------------------------------------------------------------
 */

/* 这些在 nodes/execnodes.h 中： */
/* typedef struct HashJoinTupleData *HashJoinTuple; */
/* typedef struct HashJoinTableData *HashJoinTable; */

typedef struct HashJoinTupleData
{
	/* 链接到同一桶中的下一个元组 */
	union
	{
		struct HashJoinTupleData *unshared;
		dsa_pointer shared;
	}			next;
	uint32		hashvalue;		/* 元组的哈希代码 */
	/* 元组数据，采用 MinimalTuple 格式，跟随在 MAXALIGN 边界上 */
}			HashJoinTupleData;

#define HJTUPLE_OVERHEAD  MAXALIGN(sizeof(HashJoinTupleData))
#define HJTUPLE_MINTUPLE(hjtup)  \
	((MinimalTuple) ((char *) (hjtup) + HJTUPLE_OVERHEAD))

/*
 * 如果外部关系的分布足够不均匀，我们尝试
 * 通过将与外部关系的 MCVs 相关的哈希值特别处理
 * 来优化连接。与这些哈希值匹配的内部关系元组
 * 进入“倾斜”哈希表，而具有这些哈希值的外部关系元组
 * 与该表而不是主表匹配。因此，具有这些哈希值的元组
 * 实际上被视为第一批的一部分，并且永远不会写入磁盘。
 * 倾斜哈希表的大小限制在连接允许的总内存的 SKEW_HASH_MEM_PERCENT；在构建哈希表时，
 * 如果有需要以保持在此限制之下，我们会减少
 * 特别处理的 MCV 数量。
 *
 * 注意：你可能会想知道我们为什么关注外部关系的统计数据，
 * 而不是内部关系。一个原因是外部关系通常
 * 更大，因此通过优化其最常见的值可以获得更多的 I/O 节省。
 * 此外，对于大小相似的关系，规划器倾向于将
 * 更均匀分布的关系放在内部，因此我们更可能在外部关系中找到
 * 有趣的倾斜。
 */
typedef struct HashSkewBucket
{
	uint32		hashvalue;		/* 常见的哈希值 */
	HashJoinTuple tuples;		/* 内部关系元组的链表 */
} HashSkewBucket;

#define SKEW_BUCKET_OVERHEAD  MAXALIGN(sizeof(HashSkewBucket))
#define INVALID_SKEW_BUCKET_NO	(-1)
#define SKEW_HASH_MEM_PERCENT  2
#define SKEW_MIN_OUTER_FRACTION  0.01

/*
 * 为了减少 palloc 开销，当前批次的 HashJoinTuples
 * 被打包在 32kB 的缓冲区中，而不是单独为每个元组分配内存。
 */
typedef struct HashMemoryChunkData
{
	int			ntuples;		/* 此块中存储的元组数量 */
	size_t		maxlen;			/* 块的元组缓冲区大小 */
	size_t		used;			/* 已使用的缓冲区字节数 */

	/* 指向下一个块（链表）的指针 */
	union
	{
		struct HashMemoryChunkData *unshared;
		dsa_pointer shared;
	}			next;

	/*
	 * 块的元组缓冲区在 HashMemoryChunkData 结构之后开始，
	 * 位于 OFFSET HASH_CHUNK_HEADER_SIZE（必须是最大对齐的）。
	 * 请注意，该偏移量不包括在“maxlen”或“used”中。
	 */
}			HashMemoryChunkData;

typedef struct HashMemoryChunkData *HashMemoryChunk;

#define HASH_CHUNK_SIZE			(32 * 1024L)
#define HASH_CHUNK_HEADER_SIZE	MAXALIGN(sizeof(HashMemoryChunkData))
#define HASH_CHUNK_DATA(hc)		(((char *) (hc)) + HASH_CHUNK_HEADER_SIZE)
/* 超过 HASH_CHUNK_THRESHOLD 字节的元组被放入自己的块中 */
#define HASH_CHUNK_THRESHOLD	(HASH_CHUNK_SIZE / 4)

/*
 * 对于并行哈希连接的每个批次，我们在共享内存中有一个
 * ParallelHashJoinBatch 对象来协调对它的访问。
 * 由于它们后面跟随可变大小的对象，因此它们在连续内存中排列，
 * 但不会被直接作为数组访问。
 */
typedef struct ParallelHashJoinBatch
{
	dsa_pointer buckets;		/* 哈希表桶的数组 */
	Barrier		batch_barrier;	/* 连接此批次的同步 */

	dsa_pointer chunks;			/* 加载的元组块 */
	size_t		size;			/* 内存中桶 + 块的大小 */
	size_t		estimated_size; /* 写入时桶 + 块的大小 */
	size_t		ntuples;		/* 加载的元组数量 */
	size_t		old_ntuples;	/* 重新分区前的元组数量 */
	bool		space_exhausted;

	/*
	 * 可变大小的 SharedTuplestore 对象在内存中跟随此结构。
	 * 请参阅下面的访问宏。
	 */
} ParallelHashJoinBatch;

/* 访问器用于访问跟随 ParallelHashJoinBatch 的内部批次元组存储。 */
#define ParallelHashJoinBatchInner(batch)							\
	((SharedTuplestore *)											\
	 ((char *) (batch) + MAXALIGN(sizeof(ParallelHashJoinBatch))))

/* 访问器用于访问跟随 ParallelHashJoinBatch 的外部批次元组存储。 */
#define ParallelHashJoinBatchOuter(batch, nparticipants) \
	((SharedTuplestore *)												\
	 ((char *) ParallelHashJoinBatchInner(batch) +						\
	  MAXALIGN(sts_estimate(nparticipants))))

/* 并行哈希连接批次和元组存储的总大小。 */
#define EstimateParallelHashJoinBatch(hashtable)						\
	(MAXALIGN(sizeof(ParallelHashJoinBatch)) +							\
	 MAXALIGN(sts_estimate((hashtable)->parallel_state->nparticipants)) * 2)

/* 给定基准的第 n 个 ParallelHashJoinBatch 的访问器。 */
#define NthParallelHashJoinBatch(base, n)								\
	((ParallelHashJoinBatch *)											\
	 ((char *) (base) +													\
	  EstimateParallelHashJoinBatch(hashtable) *  (n)))

/*
 * 每个后端需要少量每批状态来与每个 ParallelHashJoinBatch 交互。
 */
typedef struct ParallelHashJoinBatchAccessor
{
	ParallelHashJoinBatch *shared;	/* 指向共享状态的指针 */

	/* 每个后端的部分计数器，以减少争用。 */
	size_t		preallocated;	/* 为该后端预分配的空间 */
	size_t		ntuples;		/* 元组数量 */
	size_t		size;			/* 内存中分区的大小 */
	size_t		estimated_size; /* 磁盘上分区的大小 */
	size_t		old_ntuples;	/* 在重新分区之前有多少个元组？ */
	bool		at_least_one_chunk; /* 该后端是否分配了一个块？ */

	bool		done;			/* 标志以记住批次已经完成 */
	SharedTuplestoreAccessor *inner_tuples;
	SharedTuplestoreAccessor *outer_tuples;
} ParallelHashJoinBatchAccessor;

/*
 * 在对内部关系进行哈希时，任何参与者可能会确定
 * 是时候增加桶的数量以降低负载因子或批次
 * 以减少内存大小。这通过将增长标志设置为
 * 这些值来指示。
 */
typedef enum ParallelHashGrowth
{
	/* 当前的维度是足够的。 */
	PHJ_GROWTH_OK,
	/* 负载因子过高，因此需要添加桶。 */
	PHJ_GROWTH_NEED_MORE_BUCKETS,
	/* 内存预算将被耗尽，因此需要重新分区。 */
	PHJ_GROWTH_NEED_MORE_BATCHES,
	/* 上次重新分区没有帮助，因此不再尝试。 */
	PHJ_GROWTH_DISABLED
} ParallelHashGrowth;

/*
 * 用于协调并行哈希连接的共享状态。 这存储在 DSM 段中。
 */
typedef struct ParallelHashJoinState
{
	dsa_pointer batches;		/* ParallelHashJoinBatch 数组 */
	dsa_pointer old_batches;	/* 重新分区期间的前一代 */
	int			nbatch;			/* 现在的批次数量 */
	int			old_nbatch;		/* 先前的批次数量 */
	int			nbuckets;		/* 桶的数量 */
	ParallelHashGrowth growth;	/* 控制批次/桶增长 */
	dsa_pointer chunk_work_queue;	/* 块工作队列 */
	int			nparticipants;
	size_t		space_allowed;
	size_t		total_tuples;	/* 内部元组的总数 */
	LWLock		lock;			/* 保护上述内容的锁 */

	Barrier		build_barrier;	/* 构建阶段的同步 */
	Barrier		grow_batches_barrier;
	Barrier		grow_buckets_barrier;
	pg_atomic_uint32 distributor;	/* 负载平衡的计数器 */

	SharedFileSet fileset;		/* 共享临时文件的空间 */
} ParallelHashJoinState;

/* 用于构建批次的阶段，由 build_barrier 使用。 */
#define PHJ_BUILD_ELECTING				0
#define PHJ_BUILD_ALLOCATING			1
#define PHJ_BUILD_HASHING_INNER			2
#define PHJ_BUILD_HASHING_OUTER			3
#define PHJ_BUILD_RUNNING				4
#define PHJ_BUILD_DONE					5

/* 用于探测每个批次的阶段，由 batch_barrier 使用。 */
#define PHJ_BATCH_ELECTING				0
#define PHJ_BATCH_ALLOCATING			1
#define PHJ_BATCH_LOADING				2
#define PHJ_BATCH_PROBING				3
#define PHJ_BATCH_DONE					4

/* 在哈希过程中批次增长的阶段，用于 grow_batches_barrier。 */
#define PHJ_GROW_BATCHES_ELECTING		0
#define PHJ_GROW_BATCHES_ALLOCATING		1
#define PHJ_GROW_BATCHES_REPARTITIONING 2
#define PHJ_GROW_BATCHES_DECIDING		3
#define PHJ_GROW_BATCHES_FINISHING		4
#define PHJ_GROW_BATCHES_PHASE(n)		((n) % 5)	/* 循环阶段 */

/* 哈希时桶增长的阶段，针对 grow_buckets_barrier。 */
#define PHJ_GROW_BUCKETS_ELECTING		0
#define PHJ_GROW_BUCKETS_ALLOCATING		1
#define PHJ_GROW_BUCKETS_REINSERTING	2
#define PHJ_GROW_BUCKETS_PHASE(n)		((n) % 3)	/* 循环阶段 */

typedef struct HashJoinTableData
{
	int			nbuckets;		/* 内存哈希表中的桶数量 */
	int			log2_nbuckets;	/* 它的 log2 (nbuckets 必须是2的幂) */

	int			nbuckets_original;	/* 开始第一次哈希时的桶数量 */
	int			nbuckets_optimal;	/* 最优桶数量（每批次） */
	int			log2_nbuckets_optimal;	/* log2(nbuckets_optimal) */

	/* buckets[i] 是第 i 个内存桶中元组列表的头部 */
	union
	{
		/* 未共享数组是每批次的存储，所有元组也是如此 */
		struct HashJoinTupleData **unshared;
		/* 共享数组是每查询的 DSA 区域，所有元组也是如此 */
		dsa_pointer_atomic *shared;
	}			buckets;

	bool		keepNulls;		/* 是否真实存储无法匹配的 NULL 元组 */

	bool		skewEnabled;	/* 我们是否使用偏斜优化？ */
	HashSkewBucket **skewBucket;	/* 偏斜桶的哈希表 */
	int			skewBucketLen;	/* skewBucket 数组的大小（2的幂！） */
	int			nSkewBuckets;	/* 活动偏斜桶的数量 */
	int		   *skewBucketNums; /* 活动偏斜桶的数组索引 */

	int			nbatch;			/* 批次数 */
	int			curbatch;		/* 当前批次编号；第一次通过时为 0 */

	int			nbatch_original;	/* 开始内部扫描时的 nbatch */
	int			nbatch_outstart;	/* 开始外部扫描时的 nbatch */

	bool		growEnabled;	/* 关闭 nbatch 增加的标志 */

	double		totalTuples;	/* 从内部计划获得的元组数量 */
	double		partialTuples;	/* 我从内部计划获得的元组数量 */
	double		skewTuples;		/* 插入到 skew 元组中的元组数量 */

	/*
	 * 这些数组在哈希连接的生命周期内被分配，但仅当
	 * nbatch > 1 时才会分配。只有在我们第一次将元组写入
	 * 文件时，文件才会被打开（否则其指针保持为 NULL）。
	 * 请注意，第零个数组元素永远不会被使用，因为我们将处理
	 * 而不是转储任何批次为零的元组。
	 */
	BufFile   **innerBatchFile; /* 每批次的缓冲虚拟临时文件 */
	BufFile   **outerBatchFile; /* 每批次的缓冲虚拟临时文件 */

	/*
	 * 关于被哈希的数据类型特定哈希函数的信息。这些数组的长度
	 * 与哈希连接子句（哈希键）的数量相同。
	 */
	FmgrInfo   *outer_hashfunctions;	/* 哈希函数的查找数据 */
	FmgrInfo   *inner_hashfunctions;	/* 哈希函数的查找数据 */
	bool	   *hashStrict;		/* 每个哈希连接操作符是否严格？ */
	Oid		   *collations;

	Size		spaceUsed;		/* 当前元组占用的内存空间 */
	Size		spaceAllowed;	/* 使用的空间上限 */
	Size		spacePeak;		/* 峰值空间使用 */
	Size		spaceUsedSkew;	/* 偏斜哈希表当前的空间使用 */
	Size		spaceAllowedSkew;	/* 偏斜哈希表的上限 */

	MemoryContext hashCxt;		/* 整体哈希连接存储的上下文 */
	MemoryContext batchCxt;		/* 仅此批次存储的上下文 */

	/* 用于紧凑分配元组（到链接块中） */
	HashMemoryChunk chunks;		/* 整个批次的一个列表 */

	/* 平行哈希的共享和私有状态。 */
	HashMemoryChunk current_chunk;	/* 此后端当前的块 */
	dsa_area   *area;			/* 从中分配内存的DSA区域 */
	ParallelHashJoinState *parallel_state;
	ParallelHashJoinBatchAccessor *batches;
	dsa_pointer current_chunk_shared;
}			HashJoinTableData;

#endif							/* HASHJOIN_H */
